package com.sicheng.蓝桥.练习题.基础数论;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/7 12:34
 */
public class 欧拉筛 {
    // 欧拉筛算法
    public static void main(String[] args) {
        int n, cnt = 0;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[] prime = new int[n + 1];//存素数
        //素数的倍数全都是合数,加入过滤器中筛选
        boolean[] notPrime = new boolean[n + 1];//保证不做素数的倍数

        for (int i = 2; i <= n; i++) {
            if (!notPrime[i])//不是目前找到的素数的倍数
                prime[cnt++] = i;//找到素数~
            for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
                notPrime[i * prime[j]] = true;//找到的素数的倍数不访问
                if (i % prime[j] == 0)
                    break;//关键！！！！
            }
        }
        System.out.println(cnt);
    }

}
